//
//  Poj2431Expedition.hpp
//  DataStructuresAndAlgorithms
//
//  Created by 远平 on 2020/7/25.
//  Copyright © 2020 blue. All rights reserved.
//

#ifndef Poj2431Expedition_hpp
#define Poj2431Expedition_hpp

#include <stdio.h>

#include <queue>

class SolutionPoj2431 {
public:
    int get_minimum_stop(int L, int P, std::vector<std::pair<int, int>> &stop);
};




#endif /* Poj2431Expedition_hpp */
/*
 例6 最优加油方法
 
 已知一条公路上，有一个七点与一个终点，这之间有n个加油站；已知从这n个加油站到终点的距离d与各个加油站可以加油的量l，起点位置至终点的距离L与起始时刻邮箱中汽油量P；假设使用1个单位的汽油及走1个单位的距离，邮箱没有上限，最少加几次油，可以从起点开至终点？（如果无法到达终点，返回-1）
 
 选自 poj 2431 Expedition
 难度：Hard
 
 
 ========  ========  ========  ========  ========  ========  ========
 例6：思考
 汽车经过n个加油站，对于这n个加油站，应该在哪个加油站停下来加油，最终既能到达终点，又使得加油次数最少？
 
 若按顺序遍历加油站，则面临：
 如果在某个加油站停下来加油，可能是没必要的，有可能不进行这次加油也能到达终点；
 如果在某个加油站不停下来加油，可能由于汽油不够而无法到达终点或者后面要更多次的加油才能到达终点。
 （思考半分钟）
 
 
 ========  ========  ========  ========  ========  ========  ========
 例6：贪心规律
 何时加油最合适？
 油用光的时候加油最合适！
 
 在哪个加油站加油最合适？
 在油量最多的加油站加油最合适！
 
 
 
 ========  ========  ========  ========  ========  ========  ========
 例6：算法思路
 1.设置一个最大堆，用来存储经过的加油站的汽油量。
 2.按照从起点至终点的方向，遍历各个加油站之间的距离。
 3.每次需要走两个加油站之间的距离d，如果发现汽油不够走距离d时， 从最大堆中取出一个油量添加，直到可以足够走距离d。
 4.如果把最大堆的汽油都添加仍然不够行进距离d，则无法达到终点。
 5.当前油量P减少d。
 6.将当前加油站油量添加至最大堆。
 
 
 */
